package 链表;

import java.util.Stack;

/**
 * 请判断一个链表是否为回文链表
 * <p>
 * 1、
 * <p/>
 * User: zhaixiaolong Date:2024/1/9 10:49 ProjectName: algorithm Version: V
 */
public class 回文链表 {

    /**
     * 初始化链表
     *
     * @return
     */
    public static Node initData() {
        Node node1 = new Node();
        node1.value = 1;
        Node node2 = new Node();
        node2.value = 2;
        Node node3 = new Node();
        node3.value = 3;
        Node node4 = new Node();
        node4.value = 3;
        Node node5 = new Node();
        node5.value = 2;
        Node node6 = new Node();
        node6.value = 1;

        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        return node1;
    }

    public static void main(String[] args) {
        Boolean res = palindrome2(initData());
        System.out.println(res);
    }

    /**
     * 栈
     *
     * @param head
     * @return
     */
    public static boolean palindrome(Node head) {
        if (head.next == null) {
            return Boolean.TRUE;
        }
        Stack<Node> nodes = new Stack<>();
        Node currNode = head;
        while (currNode != null) {
            if (!nodes.isEmpty() && nodes.peek().value == currNode.value) {
                nodes.pop();
            } else {
                nodes.push(currNode);
            }
            currNode = currNode.next;
        }
        return nodes.isEmpty();
    }

    /**
     * 1、找到中间节点
     * 2、反转后半段链表
     * 3、前后链表比较
     *
     * @param head 头节点
     * @return
     */
    public static boolean palindrome2(Node head) {
        Node mindNode = mindNode(head);
        Node rev = rev(mindNode);
        while (head.next != null && rev.next != null) {
            if (head.value != rev.value) {
                return Boolean.FALSE;
            }
            head = head.next;
            rev = rev.next;
        }
        return Boolean.TRUE;
    }

    /**
     * 4、5、6
     *
     * @param head
     * @return
     */
    public static Node rev(Node head) {
        if (head == null || head.next == null) {
            return head;
        }
        // 递归：cur=6,head=5
        Node cur = rev(head.next);
        head.next.next = head;
        head.next = null;
        return cur;
    }

    public static Node mindNode(Node head) {
        Node fast = head, slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }


}
